package com.zlk.algorithm.huawei.nowcoder.dp;

import java.io.*;

/**
 * @program: algorithm
 * @ClassName ShoppingList
 * @description:
 * 1、主件附件问题
 * 2、主键最多两个附件
 * 3、买附件前必须先买主件
 * 4、每个物品只能购买一次
 *
 * 预算 n元
 * 满意度：价格与重要度的乘积的之和，
 *
 * 求满意度做高的值
 *
 *
 *
 *
 * 核心就是带依赖的关系的01背包
 *
 *
 * https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=
 *
 *
 * E:\workspace\algorithm\base\src\main\java\com\zlk\algorithm\algorithm\dynamicPlan\knapsack073\Code05_DependentKnapsack.java
 * @author: slfang
 * @create: 2024-12-20 13:05
 * @Version 1.0
 **/
public class HJ16 {

    public static int MAXN=32001;

    public static int MAXM=61;

    public static int N,M,index;


    public static int[] VALS = new int[MAXM];
    public static int[] COST = new int[MAXM];

    public static int[] MAIN = new int[MAXM];
    //最多两附件
    public static int[][] childs = new int[MAXM][2];
    public static int[] childSize = new int[MAXM];




    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(reader);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken()!=-1){
            N = (int)in.nval;
            in.nextToken();
            M = (int)in.nval;
            //编号从1 开始
            index=0;
            for (int i = 1 ,parent;i <= M; i++) {
                in.nextToken();
                COST[i] =(int) in.nval;
                in.nextToken();
                VALS[i] =(int)in.nval;
                in.nextToken();
                parent = (int)in.nval;
                if(parent!=0){
                    childs[parent][childSize[parent]++] = i;
                }else{
                    MAIN[index++] = i;
                }
            }
            int val = dp();
            out.write(""+val);
        }
        out.flush();
        out.close();
        reader.close();
    }

    private static int dp() {
        //dp含义 dp[i][j]
        // 0-i 范围不超过j预算产生的最大满意度
        //不要i： dp[i][j] = dp[i-1][j];
        //要i：dp[i][j] = dp[i-1][j-cost[i]]+val[i]
        // 取Max
        int[][] dp = new int[index+1][N+1];
        for (int i = 1,cost,val; i <= index; i++) {
            int realIndex = MAIN[i-1];
            cost = COST[realIndex];
            val = VALS[realIndex]*cost;
            for (int j = 1; j <= N; j++) {
                //不要
                int valNo = dp[i-1][j];

                //要
                int valYes = 0;
                if(j-cost>=0){
                    valYes = dp[i-1][j-cost]+val;
                    //遍历附件
                    int allCost = 0;
                    int allVals = 0;
                    //只选取单个dp
                    for (int z = 0; z < childSize[realIndex]; z++) {
                        int childRealIndex = childs[realIndex][z];
                        int costz = COST[childRealIndex];
                        int valz = VALS[childRealIndex]*costz;
                        allVals+=valz;
                        allCost+=costz;
                        if(j-cost-costz>=0){
                            valYes = Math.max(dp[i-1][j-cost-costz]+valz+val,valYes);
                        }
                    }
                    //合计dp
                    if(allVals!=0&&j-allCost-cost>=0){
                        valYes = Math.max(valYes,dp[i-1][j-allCost-cost]+allVals+val);
                    }
                }
                dp[i][j]  = Math.max(valNo,valYes);
            }
        }
        return dp[index][N];
    }

}
